/***************************************************************************
 *   Copyright (C) 2006 by Marco Bonifazi   *
 *   marcobonifazi@gmail.com   *
 *                                                                         *
 *   Permission is hereby granted, free of charge, to any person obtaining *
 *   a copy of this software and associated documentation files (the       *
 *   "Software"), to deal in the Software without restriction, including   *
 *   without limitation the rights to use, copy, modify, merge, publish,   *
 *   distribute, sublicense, and/or sell copies of the Software, and to    *
 *   permit persons to whom the Software is furnished to do so, subject to *
 *   the following conditions:                                             *
 *                                                                         *
 *   The above copyright notice and this permission notice shall be        *
 *   included in all copies or substantial portions of the Software.       *
 *                                                                         *
 *   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,       *
 *   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF    *
 *   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. *
 *   IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR     *
 *   OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, *
 *   ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR *
 *   OTHER DEALINGS IN THE SOFTWARE.                                       *
 ***************************************************************************/
 #include "elements.h"


int is_empty_list (void ** first) {
	/* Verifies if a list is empty */
	return *first == NULL;
}


/* Arcs */

void insert_arc(list_arcs** first, arc* arc){
	/* Adds an arc at the end of an arc-list */
	
	list_arcs* new_element;
	list_arcs* previous;
	list_arcs* current;
	
	new_element = malloc(sizeof( list_arcs ));
	
	if ( new_element != NULL ){		/* Malloc is ok */
		new_element->arc = arc; 	/* Create new arc_list element */
		new_element->next = NULL;
	
		previous = NULL;
		current = *first;
		
		while (current !=NULL ) {
			previous = current;
			current = current->next;
		
		}
		
		if (previous == NULL){/* Inserts at the top of the list*/
			new_element->next = *first;
			*first = new_element;
		}
		else {
			previous->next = new_element;
			new_element->next = current;
		}
	}
	else { 
		printf("%p not inserted. No memory available.\n", arc);
	}
}

int delete_arc_from_list(list_arcs** first, arc* n){
	/* Deletes an arc from arc-list*/
	int deleted = 0; /* Not any arc deleted */
	
	if (*first != NULL) {
		list_arcs* previous;
		list_arcs* current;
		list_arcs* temp;
		
		if ( (*first)->arc == n ){ /* Deleting arc is the first*/
			temp = *first;
			*first = (*first)->next;
			free(temp);
			temp = NULL;
			deleted = 1;
		}
		else {
			previous = *first; 
			current = (*first)->next;
		
			while ( current != NULL && current->arc != n){
				previous = current;
				current = current->next;
			}
			if ( current != NULL ){ /* While didn't break for NULL */
				temp = current;
				previous->next = current->next;
				free (temp);
				temp = NULL;
				deleted = 1;
			}
		}
	}
	/*if (deleted == 0 ) printf("One or more nodes are deleted from the list\n");*/
	return deleted;
}

int delete_real_arc_from_list(list_real_arcs** first, list_nodes* n){
	/* Deletes an arc from arc-list */
	int deleted = 0; /* Not any arc deleted */
	
	if (*first != NULL){
		list_real_arcs* previous;
		list_real_arcs* current;
		list_real_arcs* temp;
	
		if ( (*first)->nodes == n ){ /* Deleting arc is the first*/
			temp = *first;
			*first = (*first)->next;
			free(temp);
			temp = NULL;
			deleted = 1;
		}
		else {
			previous = *first; 
			current = (*first)->next;
		
			while ( current != NULL && current->nodes != n){
				previous = current;
				current = current->next;
			}
			if ( current != NULL ){ /* While didn't break for NULL */
				temp = current;
				previous->next = current->next;
				free(temp);
				temp = NULL;
				deleted = 1;
			}
		}
	}
	/*if (deleted == 0 ) printf("One or more real nodes are deleted from the list\n");*/
	return deleted;
}

int length_list_arcs( list_arcs* list) {
	/* Returns the length of list_arcs  */
	
	int c = 0;
	
	while ( list != NULL ){
		list = list->next;
		c ++;
	}
	return c;
}

int is_in_list_arcs(list_arcs* in_arcs, arc* arc){
	/* It verifies if arc is in list_arcs, analizing the position of the nodes */
	
	int present = 0; /* Not present */

	node *n1, *n2, *n_1, *n_2; /* n1 and n2 are the nodes of an arc in the list, n_1, n_2 are nodes of the input arc*/

	while ( in_arcs != NULL ){
		n1 = in_arcs->arc->n1;
		n2 = in_arcs->arc->n2;
		n_1 = arc->n1;
		n_2 = arc->n2;
		
		if ( (n1->position[0] == n_1->position[0] && n1->position[1] == n_1->position[1] && n2->position[0] == n_2->position[0] && n2->position[1] == n_2->position[1]) ||
		(n1->position[0] == n_2->position[0] && n1->position[1] == n_2->position[1] && n2->position[0] == n_1->position[0] && n2->position[1] == n_1->position[1])){
			present = 1; /* The node is present in the list */
			break;
		}
		in_arcs = in_arcs->next;
	}
	return present;
}

list_arcs* copy_list_arcs( list_arcs* list ){
	/* Returns a copy of a arc list */

	list_arcs *first, *temp;
	
	if ( list != NULL ){
		temp = malloc( sizeof( list_arcs ) );
		first = temp;
		temp->arc = list->arc;
		
		while ( list->next != NULL ){
			temp->next = malloc( sizeof( list_arcs ));
			temp = temp->next;
			list = list->next;
			temp->arc = list->arc;
			
		}
		temp->next = NULL;
	}
	
	else { 
		first = NULL;
	}

	return first;
}

list_arcs* conc_list_arcs(list_arcs* l1, list_arcs** l2){
	/* Concatenates two different list_arcs and returns the fusion one in the following way: 
	 * scans the second list and inserts arcs in the first one, then delete each element of the second list */

	list_arcs* temp1 = copy_list_arcs(l1);

	while ( *l2 != NULL ){
		insert_arc( &temp1, (*l2)->arc );
		delete_arc_from_list(l2, (*l2)->arc);
	}

	return temp1;
}
 
void conc_list_arcs2(list_arcs* l1, list_arcs** l2){
	/* Concatenates two different list_arcs and returns the fusion one. 
	 * The elements of the first list are appended at the beginning of the second, which is the list to return */
	list_arcs* first = l1;
	
	while ( l1 != NULL && l1->next != NULL ){
		l1 = l1->next;
	}
	if (l1 == NULL)
		l1 = *l2;
	else
	    l1->next = *l2;
   *l2 = first;
}

arc* create_arc(node* n1, node*n2){
	/* It creates and returns an arc */
	arc* new_arc = malloc(sizeof( arc ));
	new_arc->n1 = n1;
	new_arc->n2 = n2;
	return new_arc;
}

list_arcs* make_arcs(node* n, list_nodes* ln, list_nodes* visited ) {
	/* Given a node and his neighbours, it creates a list of arcs only if the node isn't in visited list
	  (to avoid a copy of the same arc in reverse direction */

	list_arcs* arcs = NULL;
	arc* arc1 = NULL;
	
	
	while( ln != NULL ){
		
		if (is_in_list_nodes( visited, ln->node) ){
			arc1 = malloc(sizeof( arc ));
			arc1->n1 = n;
			arc1->n2 = ln->node;
			
			insert_arc( &arcs, arc1 ); /* Inserts the arc in arcs list */
				
		}
		ln = ln->next;		
	}
	
	return arcs;
}

void free_list_arcs( list_arcs* list ){
	/* It frees memory occupied by list_nodes without deleting the arc*/
	
	while ( list != NULL ){
		//arc* temp = list->arc;
		delete_arc_from_list(&list, list->arc);
		//printf ("arco\n");
		//free(temp);
	}
}

void free_list_real_arcs( list_real_arcs* list ){
	/* It frees memory occupied by list_real_arcs, deleting the list_nodes */

	while ( list != NULL ){
		
		list->n_start = NULL;
		list->n_end = NULL;
		list_nodes* temp = list->nodes;
		delete_real_arc_from_list(&list, list->nodes);
		
		free_list_nodes(temp, 0);
		temp = NULL;

	}

};

/* Nodes */

void insert_node(list_nodes** first, node* node){
	/* Add a node at the end of a node-list */
	list_nodes* new_element = NULL;
	list_nodes* previous = NULL;
	list_nodes* current = NULL;
	
	new_element = malloc(sizeof( list_nodes ));
	
	if ( new_element != NULL ){/* Malloc is ok */
		new_element->node = node; /* Create new node_list element */
		new_element->next = NULL;
	
		previous = NULL;
		current = *first;
		
		while (current != NULL ) {
			previous = current;
			current = current->next;
		}
		
		if (previous == NULL){/* Inserts at the top of the list*/
			new_element->next = *first;
			*first = new_element;
		}
		else {
			previous->next = new_element;
			new_element->next = current;
		}
	}
	else {
		printf("%p not inserted. No memory available.\n", node);
	}
}

void insert_node_at_top(list_nodes** first, node* node){
	/* Add a node at the end of a node-list */
	list_nodes* new_element = NULL;

	
	new_element = malloc(sizeof( list_nodes ));
	
	if ( new_element != NULL ){/* Malloc is ok */
		new_element->node = node; /* Create new node_list element */
		new_element->next = *first;
		*first = new_element;

	}
	else {
		printf("%p not inserted. No memory available.\n", node);
	}
}

int delete_node_from_list(list_nodes** first, node* n){
	int deleted = 0; /* Not any node deleted */
	
	if (*first != NULL){
		list_nodes* previous;
		list_nodes* current;
		list_nodes* temp;
		
		if ( (*first)->node == n ){ /* Deleting node is the first */
			temp = *first;
			*first = temp->next;
			free(temp);
			temp = NULL;
			deleted = 1;

		}
		else {
			previous = *first; 
			current = (*first)->next;
		
			while ( current != NULL && current->node != n){
				previous = current;
				current = current->next;
			}
			if ( current != NULL ){ /* While didn't break for NULL */
				temp = current;
				previous->next = current->next;
				free(temp);
				temp = NULL;
				deleted = 1;
			}
		}
	}
	/*if ( deleted == 1 ) 
		printf("One or more node are deleted from the list\n");*/
	return deleted;
}

list_nodes* get_neighbours(node* n, int x, int y){
	/* Returns neighbours of a node in the cell (x,y)*/
	list_nodes* neighs_to_return = NULL;
	list_nodes* neighs = n->neighbours;
	
	while ( neighs != NULL ){
		if ( neighs->node->position[0] == x && neighs->node->position[1] == y )
			insert_node(&neighs_to_return, neighs->node);
		neighs = neighs->next;
	}
		
	return neighs_to_return;
};

int length_nodes_list(list_nodes* list){
	int i = 0;
	
	while ( list != NULL){
		list = list->next;
		i ++;
	}
	return i;
}

void free_node(node** n, int mode){
	if ( *n != NULL ){
		
		if (mode){
			free_list_nodes((*n)->neighbours, 0 );
			(*n)->neighbours = NULL;
		}
		//if ((*n)->label != NULL && !strcmp((*n)->label,""))
			//free((*n)->label);
		(*n)->label = NULL;
		(*n)->n1 = NULL;
		(*n)->n2 = NULL;
		(*n)->neighbours = NULL;
		free((*n));
		*n = NULL;

	}


}

void free_list_nodes( list_nodes* list, int mode ){
	/* It frees memory occupied by list_nodes */
	
	while ( list != NULL )
		delete_node_from_list(&list, list->node);
	
		/*temp = list;
		list = list->next;
		free(temp);
		temp = NULL;
*/
		//temp = temp->next;
	

}

node* create_node(char* label, int type){
	/* It creates a new node with not defined positions*/
	node* temp = malloc( sizeof( node ) );

	temp->position[0] = -1;
	temp->position[1] = -1;
	temp->neighbours = NULL;
	temp->label = label;
	temp->type = type;
	//temp->n1 = NULL;
	//temp->n2 = NULL;
	return temp;
}

node* create_node_in_cell(grid* gr, char* label, int type, int x, int y){
	node* temp = malloc( sizeof( node ) );
	temp->position[0] = -1;
	temp->position[1] = -1;

	temp->neighbours = NULL;
	temp->label = label;
	temp->type = type;
	//temp->n1 = NULL;
	//temp->n2 = NULL;
	put_node_in_cell ( temp, gr, x, y );
	return temp;
}

list_nodes* copy_list_nodes( list_nodes* list ){
	/* Returns a copy of a node list */

	list_nodes *first, *temp, *temp_list;
	temp_list = list;
	
	if ( temp_list != NULL ){
		temp = malloc( sizeof( list_nodes ) );
		first = temp;
		temp->node = temp_list->node;
		
		while ( temp_list->next != NULL ){
			temp->next = malloc( sizeof( list_nodes ));
			temp = temp->next;
			temp_list = temp_list->next;
			temp->node = temp_list->node;
			
		}
		temp->next = NULL;
	}
	
	else { 
		first = NULL;
	}

	return first;	

}


int is_in_list_nodes(list_nodes* first, node* n){
	/* It verifies if node n is in the list_nodes*/
	int present = 0; /* Not present */
	list_nodes* temp_node = first;

	while ( temp_node != NULL && temp_node->node != n)
		temp_node = temp_node->next;
		
	if (temp_node != NULL )
		present = 1; /* The node is present in the list */

	return present;
}

void make_neighbour( node* n1, node* neigh ){
	/* Sets n1 node as a neighbour of neigh node and viceversa*/
		
		//list_nodes* temp = n1->neighbours;
		insert_node(&(n1->neighbours), neigh);
		/*
		n1->neighbours = malloc(sizeof(list_nodes));
		n1->neighbours->node = neigh;
		n1->neighbours->next = temp;
		*/
		//list_nodes* temp2 = neigh->neighbours;
		insert_node(&(neigh->neighbours), n1);
		/*
		neigh->neighbours = malloc(sizeof(list_nodes));
		neigh->neighbours->node = (node*)n1;
		neigh->neighbours->next = temp2;
		*/
}

void clear_node_neighbours(node* n){
	/* It clears neighbours list of node n*/
	free_list_nodes(n->neighbours,0 );
	n->neighbours = NULL;
	//while ( n->neighbours != NULL) /* Clear neighbours list of node n */
	//	delete_node_from_list( &(n->neighbours), n->neighbours->node );
	
};

void conc_list_nodes2(list_nodes* l1, list_nodes** l2){
	/* Concatenates two different list_nodes and returns the fusion one
	 * The elements of the first list are appended at the beginning of the second, which is the list to return */
	list_nodes* first = l1;
	
	while ( l1 != NULL && l1->next != NULL ){
		l1 = l1->next;
	}
	if (l1 == NULL)
		l1 = *l2;
	else
	    l1->next = *l2;
   *l2 = first;
}

list_nodes* conc_nodes(list_nodes* l1, list_nodes* l2){
	/* Concatenates two different list_nodes and returns the fusion one*/
	list_nodes* temp = copy_list_nodes(l1);
	list_nodes* first = temp;
	
	while ( temp != NULL ){
		insert_node(&l2, temp->node);
		
		temp = temp->next;
	}
	free_list_nodes(first, 0);
	first = NULL;
	return l2;
}

list_nodes* conc_nodes_to_set(list_nodes* l1, list_nodes* l2){
	/* Concatenates two different list_nodes and returns the fusion one, verifying to delete duplicates */
	list_nodes* temp1 = copy_list_nodes(l1);
		
	while ( l2 != NULL ){
		if ( !is_in_list_nodes( temp1, l2->node  ) ){
			insert_node(&temp1, l2->node);
			delete_node_from_list(&l2, l2->node);
		}
		else
			l2 = l2->next;
	}

	return temp1;
}

int is_in_positions(int positions[4][2], int num_pos, int x, int y){
	/* Verifies if a node is in one position of positions array*/
	int in_pos = 0;
	
	if ( positions != NULL){
		int i = 0;
		
		while (i < 4 && positions[i][0] != -1   ){
			
			if (x == positions[i][0] && y == positions[i][1]){
				in_pos = 1;
				
			}
			i++;
		}
	}
	else 
		in_pos = -1;
	
	return in_pos;
}

void near_positions(grid* gr, int positions[4][2], int x, int y ){
	/* Returns grid positions around an x,y tuple of coordinates. 
	 * It considers the special cases of positions at grid borders, 
	 * putting NULL some position when a cell is at the borders*/
	
	if (gr != NULL){
		int width = gr->dims[0];
		int height = gr->dims[1];
		
		int i = 0;
		
		if ( x > 0 ){
			positions[i][0] = x-1;
			positions[i][1] = y;
			i++;
			
		}
		if ( x < height ){
			positions[i][0] = x+1;
			positions[i][1] = y;
			i++;
			
		}
		if ( y > 0 ){
			positions[i][0] = x;
			positions[i][1] = y-1;
			i++;
			
		}
		if ( y <  width){
			positions[i][0] = x;
			positions[i][1] = y+1;
			i++;
			
		}
		int i2 = i;
		for ( i2 = i; i2 < 4; i2++ ){			/* Make NULL the rest of array positions */
			positions[i][0] = -1;
			positions[i][1] = -1;
		}
	}
}

int has_neighbour(node* n, int x, int y){
	/* Given a node n, estabilishes if it has neighbours with position (x,y) */
	list_nodes* temp = n->neighbours;
	int has_neigh = 0;
	
	while (temp != NULL && (temp->node->position[0] != x || temp->node->position[1] != y ))
		temp = temp->next;
	if (temp == NULL )//temp->node->position[0] == x && temp->node->position[1] == y ){
		has_neigh = 0;
	else
		has_neigh = 1;

	
	return has_neigh;
}

/* Grids */

grid* create_2d_empty_grid( int width, int height ){
	/* Creates a width x, height y grid with all cells to NULL and returns a pointer to it */
	
	grid* temp = malloc( sizeof( grid ) );
	temp->dims[0] = width;
	temp->dims[1] = height;
	temp->cells = malloc( sizeof( list_nodes** )* height ); /* Create a node grid */
	int row;
	int col;
	
	for ( row = 0; row < height; row ++ ){
		temp->cells[row] = malloc( sizeof( list_nodes* )*width );

		for ( col = 0; col < width; col ++ ){
			temp->cells[row][col] = NULL; /*A cell is a pointer to node structure, here all cells are NULL pointer*/
		};
	};
	return temp;
};

void put_node_in_cell(node* n1, grid* gr, int x, int y ){
	/* Puts a node in a free grid cell, at (x, y) position */
	
	insert_node(&(gr->cells[x][y]), n1);

	n1->position[0] = x;
	n1->position[1] = y;
}

int free_grid(grid* gr){
	int width = gr->dims[0];
	int height = gr->dims[1];

	int r,c;

	list_nodes* temp;
	for (r = 0; r < height; r++){
	
		for (c = 0; c < width; c++){
			temp = gr->cells[r][c];
			
			while (temp != NULL ){
				free_list_nodes(temp->node->neighbours, 0);
				temp->node->neighbours = NULL;
				temp = temp->next;
			}
		}
	}

	for (r = 0; r < height; r++){
	
		for (c = 0; c < width; c++){
			free_list_nodes(gr->cells[r][c], 1);
			gr->cells[r][c] = NULL;

		}
		free(gr->cells[r]);
		gr->cells[r] = NULL;
	}
	free(gr->cells);
	gr->cells = NULL;
	free(gr);
	gr = NULL;
	return 1;
}

void delete_nodes_from_cell (grid* gr, int x, int y){
	list_nodes* list = gr->cells[x][y];
	
	while ( list != NULL)
		delete_node_from_list(&(list), list->node );
	/* free( gr->cells[x][y] ); */
}

int is_real_node_in_cell(grid* gr, int x, int y){
	/* It estabilishes if there is a real node in a cell */

	int is_node = 0;
	list_nodes* list = gr->cells[x][y];

	while( list != NULL ){
		if (list->node->type == 1 ) is_node = 1;
	
		list = list->next;
	}

	return is_node;
}

/* Printing */

void print_list_nodes(list_nodes* list){
	if ( list == NULL ){
		printf("Lista vuota\n");
	}
	else {
		list_nodes * temp = list;
		printf("Stampa lista nodi\n");
		
		while ( temp != NULL){
			printf("Nodo %i, (%i, %i)\n", temp->node->type,temp->node->position[0], temp->node->position[1]);
			if (temp->node->n1 != NULL || temp->node->n2 != NULL)
			printf("	Arco (%i, %i), (%i, %i)\n", temp->node->n1->position[0], temp->node->n1->position[1], temp->node->n2->position[0], temp->node->n2->position[1]);
			temp = temp->next;
		
		
		}
		temp = NULL;
	}
}

void print_real_arcs( list_real_arcs* real_arcs ){
	list_real_arcs* temp_arcs = real_arcs;
	int i = 1;
	node *n1, *n2, *temp_n1,*temp_n2, *c_node;
	list_nodes* temp;
	
	while ( temp_arcs != NULL ){
		n1 = temp_arcs->n_start;
		n2 = temp_arcs->n_end;
		
		printf("Arc %i - N1 (%i,%i) , N2 (%i,%i)\n", i, n1->position[0], n1->position[1], n2->position[0], n2->position[1]);
		temp = temp_arcs->nodes;
		temp = temp->next;

		while ( temp->next != NULL){
			c_node = temp->node;
			temp_n1 = c_node->n1;
			temp_n2 = c_node->n2;
			if (temp_n1 != NULL && temp_n2 != NULL)
			printf("\tInternal node (%i,%i) has labels (%i,%i), (%i,%i)\n", c_node->position[0], c_node->position[1], temp_n1->position[0], temp_n1->position[1], temp_n2->position[0], temp_n2->position[1] );
			temp = temp->next;
		}
		
		i ++;
		temp_arcs = temp_arcs->next;
	}

}

void print_list_arcs(list_arcs* list){

	
	while ( list != NULL ){
		printf("Arco: (%i,%i)-(%i,%i)\n", list->arc->n1->position[0], list->arc->n1->position[1], list->arc->n2->position[0], list->arc->n2->position[1]);
		list = list->next;
	}
	list = NULL;
}

void print_2d_grid( grid* gr ){
	int width = gr->dims[0];
	int height = gr->dims[1];
	printf("Print of a %i, %i grid\n", width, height);
	int row;
	int col;
	list_nodes* l_node;
	
	for ( col = 0; col <= width; col++)
		printf("   %i   ",col );
	
	printf("\n\n\n");

	for ( row=0; row < height; row++){
		printf( "   %i   ", row + 1 );

	
		for ( col = 0; col < width; col++){
			l_node = gr->cells[row][col];
			
			if ( l_node == NULL ){
			    printf("  %d   ", 0);
			}
			else
				printf("  %d   ", 1);
			/*while ( l_node != NULL ){
				l_node = l_node->next;
			}*/
					
		}
		printf("\n\n\n");	
	}
	printf("\n");
};

void print_labels(node* n ){
	if ( n->n1 == NULL && n->n2 == NULL){
		printf("Real Node (%i,%i)\n", n->position[0], n->position[1]);
	}
	else 
		printf("Node (%i,%i), labels (%i, %i)-(%i, %i) \n", n->position[0], n->position[1], n->n1->position[0], n->n1->position[1], n->n2->position[0], n->n2->position[1]);
}
